import java.util.HashMap;
import java.util.Map;

public class Main {
    /**
     * 坏了的计算器
     */
//    class Solution {
//        public int brokenCalc(int startValue, int target) {
//            int ret = 0;
//            while(target > startValue) {
//                if(target % 2 != 0) target++;
//                else target /= 2;
//                ret++;
//            }
//            return ret + startValue - target;
//        }
//    }

    /**
     * 单调递增数字
     */
//    class Solution {
//        public int monotoneIncreasingDigits(int n) {
//            char[] ch = Integer.toString(n).toCharArray();
//            //1寻找第一个递减的位置
//            int i = 0;
//            int m = ch.length;
//            while(i + 1 < m && ch[i] <= ch[i + 1]) i++;
//            //判断一下特殊情况
//            if(i == m - 1) return n;
//            //2往后找相同的数
//            while(i - 1 >= 0 && ch[i] == ch[i - 1]) i--;
//            ch[i]--;
//            //3剩下的所有数都改为9
//            for(int j = i + 1; j < m; j++) {
//                ch[j] = '9';
//            }
//            return Integer.parseInt(new String(ch));
//        }
//    }
/**
 * 合并区间
 */
//    class Solution {
//        public int[][] merge(int[][] intervals) {
//            //先按照左端点将原数组进行排序--->将具有想用性质的元素集在一起--->能合并的区间是连续的
//            Arrays.sort(intervals, (v1,v2)->{
//                return v1[0] - v2[0];
//            });
//            //2. 将所有的有相交的区间合并起来--->求并集
//            int left = intervals[0][0];
//            int right = intervals[0][1];
//            List<int[]> ret = new ArrayList<>();
//            for(int i = 1; i < intervals.length; i++) {
//                int a = intervals[i][0];
//                int b = intervals[i][1];
//                if(a <= right) {
//                    //求并集
//                    right = Math.max(right, b);
//                }else{
//                    //连续合并的区间断开--->将多个区间合并后的区间 即 [left, right] 放到ret中
//                    ret.add(new int[]{left,right});
//                    left = a;
//                    right = b;
//                }
//            }
//            //特别注意: 最后一个区间是不会在for循环中加入到ret的需要手动加
//            ret.add(new int[]{left,right});
//            return ret.toArray(new int[0][]);
//
//        }
//    }


/**
 * 无重叠区间
 */
//class Solution {
//    public int eraseOverlapIntervals(int[][] intervals) {
//        //1.按照左端点排序
//        Arrays.sort(intervals, (v1, v2) -> {
//            return v1[0] - v2[0];
//        });
//        int left = intervals[0][0];
//        int right = intervals[0][1];
//        int ret = 0;
//        for(int i = 1; i < intervals.length; i++) {
//            int a = intervals[i][0];
//            int b = intervals[i][1];
//            if(a < right) {
//                //需要移除右端点较大的区间
//                if(right > b) {
//                    left = a;
//                    right = b;
//                }
//                ret++;
//            } else {
//                left = a;
//                right = b;
//            }
//        }
//        return ret;
//    }
//}

    /**
     * 最少数目的箭射击所有的气球
     */
//    class Solution {
//    public int findMinArrowShots(int[][] points) {
//        Arrays.sort(points, (v1, v2) -> {
//            //这里最好不要用减法 容易越界
//            return v1[0] > v2[0] ? 1 : -1;
//        });
//        int right = points[0][1];
//        int ret = 0;
//        for (int i = 1; i < points.length; i++) {
//            int a = points[i][0];
//            int b = points[i][1];
//            if (a <= right) {
//                //可以求交集
//                right = Math.min(right, b);
//            } else {
//                //当前的一个连续的可以用一支箭射破几个区间到此为止
//                ret++;
//                right = b;
//            }
//
//        }
//        return ret + 1;
//    }
//}

    /**
     * 整数替换---递归 + 记忆化搜索解决
     */
//    class Solution {
//        HashMap<Long, Integer> hash;
//
//        public int integerReplacement(int n) {
//            hash = new HashMap<>();
//            return dfs(n);
//        }
//
//        //使用一个hash表来装已经递归过的数---->记忆化搜索
//
//        int dfs(long n) {
//            if (hash.containsKey(n)) {
//                return hash.get(n);
//            }
//            if (n == 1)
//                return 0;
//            //递归之前先去备忘录里找找看是否之前已经算过了
//
//            //是偶数
//            if (n % 2 == 0) {
//                hash.put(n, dfs(n / 2) + 1);
//                return 1 + dfs(n / 2);
//            } else {
//                //奇数
//                hash.put(n, Math.min(dfs(n + 1), dfs(n - 1)) + 1);
//                return Math.min(dfs(n + 1), dfs(n - 1)) + 1;
//            }
//        }
//    }

    /**
     * 贪心解法---比较难想
     */
//    class Solution {
//        public int integerReplacement(int _n) {
//            long n = _n;
//            //贪心解法: n % 4 = 1 最后两位 是 01 奇数采取 - 1
//            // n % 4 = 3 最后两位是 11 采取 + 1
//            //对于偶数我们只能 / 2 但是对于奇数我们有两策略 +1 -1  如果我们对于一个n 我们知道该 +1 还是-1
//            //那么我们就可以很大程度的降低时间
//            int ret = 0;
//            while (n > 1) {
//                if (n % 2 == 0) {
//                    //偶素
//                    n = n / 2;
//                } else {
//                    //奇数
//                    //特殊情况 如果这个奇数是 3 那么直接 那么他需要两步
//                    if (n == 3) {
//                        ret += 2;
//                        break;
//                    }
//                    n = n % 4 == 1 ? n - 1 : n + 1;//此处会越界
//                }
//                ret++;
//            }
//            return ret;
//        }
//    }

    /**
     * 俄罗斯套娃信封问题----重写排序 + 贪心 + 二分
     */
//    class Solution {
//        public int maxEnvelopes(int[][] envelopes) {
//            int n =envelopes.length;
//            Arrays.sort(envelopes, (v1, v2) ->{
//                //左端点一样的按照右端点降序排
//                //不一样的按照左端点升序排
//                if(v1[0] == v2[0]) {
//                    return v2[1] - v1[1];
//                }else{
//                    return v1[0] - v2[0];
//                }
//            });
//            //贪心 + 二分
//            //将所有的右端点数据拿出来-->求最长递增子序列
//            List<Integer> list = new ArrayList<>();
//            list.add(envelopes[0][1]);
//            for(int i = 0; i < n; i++) {
//                //只需要研究右端点的数据即可
//                int a = envelopes[i][1];
//                //如果这个数比最后一个数都大 那就直接插到最后一个位置
//                if(a > list.get(list.size() - 1 )){
//                    list.add(a);
//                }
//                //二分查找合适位置插入
//                int left = 0;
//                int right = list.size() - 1;
//                while(left < right) {
//                    int index = (left+right) / 2;
//                    if(a > list.get(index)) {
//                        left = index + 1;
//                    }else{
//                        right = index;
//                    }
//                }
//                //将left 位置的元素替换掉
//                list.set(left, a);
//            }
//            return list.size();
//        }
//    }

    /**
     * 堆箱子
     */
//    class Solution {
//        public int pileBox(int[][] box) {
//            //先排序
//            Arrays.sort(box, (v1, v2) ->{
//                return v1[0] - v2[0];
//            });
//            int n = box.length;
//            int[] dp = new int[n];
//            //初始化dp
//            for(int i = 0; i < n; i++) {
//                dp[i] = box[i][2];
//            }
//            for(int i = 0; i < n; i++) {
//                for(int j = 0; j < i; j++) {
//                    if(box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2]) {
//                        dp[i] = Math.max(dp[i], dp[j] + box[i][2]);
//                    }
//                }
//            }
//            int ret = 0;
//            for(int x : dp) {
//                ret = Math.max(ret,x);
//            }
//            return ret;
//        }


    /**
     * 可被三整除的最大数和
     */
//    class Solution {
//        public int maxSumDivThree(int[] nums) {
//            //思路: 正难则反 + 贪心 + 分情况讨论
//            int n = nums.length;
//            int sum = 0;
//            //假设x1 y1 是最小 y1 y2 是次小
//            //在此处有一些细节: 就是当没有 % 3 = 1 || % 3 = 2的数时候 最后 sum - x1 - x2 会越界 此处不能使用Integer.MAX_VALUE
//            //int p = Integer.MAX_VALUE;
//            int INF = 0x3f3f3f3f;
//            int x1 = INF, x2 = INF, y1 = INF, y2 = INF;
//            //可以先将数组中 %3 =1 = 2的最小数 + 次小数 先找出来
//            for(int x : nums) {
//                sum += x;
//                if(x % 3 == 1) {
//                    if(x < x1) {
//                        x2 = x1;
//                        x1 = x;
//                    } else if(x >= x1 && x <= x2) {
//                        x2 = x;
//                    }
//                }else if(x % 3 == 2){
//                    if(x < y1) {
//                        y2 = y1;
//                        y1 = x;
//                    } else if(x >= y1 && x <= y2) {
//                        y2 = x;
//                    }
//                }
//            }
//            if(sum % 3 == 0) {
//                //直接返回
//                return sum;
//            } else if(sum % 3 == 1) {
//                //模3 = 1 的发生场景有两种 1: 其他的模3 =1 的都可以 33 组合 然后 % 3 =0 唯独留有一个 % 3 = 0 的落单了
//                //那么删除一个最小的 即可
//                //2: 剩下两个 % 3 = 2 的 然后加起来 % 3 = 1 删除两个 % 3 = 2的即可
//                return Math.max(sum - x1, sum - y1 -y2);
//            } else {
//
//                //sum % 3 == 2
//                return Math.max(sum - x1 - x2, sum -y1);
//            }
//        }
//    }
//    }

    /**
     *
     *
     */
//    class Solution {
//        public int[] rearrangeBarcodes(int[] barcodes) {
//            int n = barcodes.length;
//            HashMap<Integer, Integer> hash = new HashMap<>();
//            int maxVal = 0; //记录下出现次数最大的数是谁
//            int maxCount = 0; //记录最大出现次数
//            for(int x : barcodes) {
//                hash.put(x, hash.getOrDefault(x, 0) + 1);
//                if(hash.get(x) > maxCount) {
//                    //更新最大出现次数
//                    maxCount = hash.get(x);
//                    maxVal = x;
//                }
//            }
//            //先排出现次数最多的数
//            int index = 0;
//            int[] ret = new int[n];
//            for(int i = 0; i < maxCount; i++) {
//                ret[index] = maxVal;
//                index += 2;
//            }
//            //排剩下的数
//            hash.remove(maxVal);
//            for(int key : hash.keySet()) {
//                for(int i = 0; i < hash.get(key); i++) {
//                    if(index >= n) index = 1;
//                    ret[index] = key;
//                    index += 2;
//                }
//            }
//            return ret;
//        }
//    }

    /**
     * 重构字符串
     */
//    class Solution {
//        public String reorganizeString(String s) {
//            int n = s.length();
//            char[] charArray = s.toCharArray();
//            //统计每个字符出现的次数
//            char maxChar = 0;
//            int maxCount = 0;
//            HashMap<Character, Integer> hash = new HashMap<>();
//            for(char ch : charArray) {
//                hash.put(ch, hash.getOrDefault(ch, 0) + 1);
//                if(hash.get(ch) > maxCount) {
//                    maxChar = ch;
//                    maxCount = hash.get(ch);
//                }
//            }
//            int index = 0;
//            char[] ret = new char[n];
//            //特判一下
//            if(maxCount > (n + 1) / 2) {
//                //这种情况是没有解的
//                return "";
//            }
//            //先排出现次数最多的字符
//            for(int i = 0; i < maxCount; i++) {
//                ret[index] = maxChar;
//                index += 2;
//            }
//            //先从hash表中删除已经排好的
//            hash.remove(maxChar);
//            //排其他字符
//
//            for(char key : hash.keySet()) {
//                for(int i = 0; i < hash.get(key); i++) {
//                    if(index >= n) index = 1;
//                    ret[index] = key;
//                    index += 2;
//                }
//            }
//            return new String(ret);
//        }
//    }


}
